#include "linearList.h"

// 顺序表打印
void sequenceList::print()
{
    std::cout << curNumberOfItem << ":";

    for (int i = 0; i < curNumberOfItem - 1; i++)
    {
        std::cout << myList[i] << ",";
    }

    std::cout << myList[curNumberOfItem - 1] << std::endl;
}

// 顺序表构造（顺序表容量，初始化数组长度，初始化数组值）
sequenceList::sequenceList(const int &maxCapcity, const int &curNumberOfItem, float myList[])
{
    this->maxCapcity = maxCapcity;
    this->curNumberOfItem = curNumberOfItem;
    this->myList = new float[maxCapcity];
    for (int i = 0; i < curNumberOfItem; i++)
    {
        this->myList[i] = myList[i];
    }
}

// 顺序表析构
sequenceList::~sequenceList()
{
    delete[] myList;
}

// 顺序表添加元素，添加元素顺序表尾，成功返回true，失败返回false
bool sequenceList::addItem(const float &val)
{
    if (curNumberOfItem >= maxCapcity)
    {
        return false;
    }

    myList[curNumberOfItem] = val;
    curNumberOfItem++;
    return true;
}

// 顺序表插入元素，插入元素到index位置，成功返回true，失败返回false
bool sequenceList::insertItem(const int &index, const float &val)
{
    if (index < 0 || index > curNumberOfItem)
    {
        return false;
    }

    if (curNumberOfItem >= maxCapcity)
    {
        return false;
    }

    for (int i = curNumberOfItem; i > index; i--)
    {
        myList[i] = myList[i - 1];
    }

    myList[index] = val;
    curNumberOfItem++;
    return true;
}

// 顺序表删除元素，返回删除位置，找不到返回-1
int sequenceList::deleteItem(const float &val)
{
    for (int i = 0; i < curNumberOfItem; i++)
    {
        if (myList[i] == val)
        {
            for (int j = i; j < curNumberOfItem; j++)
            {
                myList[j] = myList[j + 1];
            }
            curNumberOfItem--;
            return i;
        }
    }
    return -1;
}

// 顺序表查找元素（按序号查找），成功返回true，值放在val中，失败返回false
bool sequenceList::locate(const int &index, float &val)
{
    if (index < 0 || index >= curNumberOfItem || index >= maxCapcity)
    {
        return false;
    }
    val = myList[index];
    return true;
}

// 顺序表查找元素（按值查找），返回找到位置，找不到返回-1
int sequenceList::locate(const float &val)
{
    for (int i = 0; i < curNumberOfItem; i++)
    {
        if (myList[i] == val)
        {
            return i;
        }
    }
    return -1;
}

// 顺序表倒序排列（使用原空间）
void sequenceList::reverse()
{
    float tmp;
    for (int i = curNumberOfItem / 2; i < curNumberOfItem; i++)
    {
        tmp = myList[i];
        myList[i] = myList[curNumberOfItem - i - 1];
        myList[curNumberOfItem - i - 1] = tmp;
    }
}

/*-----------------------------------------------------------------*/

// 构造节点
listNode::listNode(float nodeData, listNode *succ)
{
    this->data = nodeData;
    this->next = succ;
}

// 析构节点
listNode::~listNode()
{
}

/*-----------------------------------------------------------------*/

// 链表打印
void linkList::print()
{
    cur_Node = firstNode;

    std::cout << listSize << ":";

    while (cur_Node != lastNode)
    {
        if (cur_Node->next == lastNode)
            std::cout << cur_Node->next->data << std::endl;
        else
        {
            std::cout << cur_Node->next->data << ",";
        }

        cur_Node = cur_Node->next;
    }
}

// 构造链表，初始化数组长度，初始化数组
linkList::linkList(const int &listSize, float data[])
{
    this->listSize = listSize;
    firstNode = new listNode();
    lastNode = firstNode;
    for (int i = 0; i < listSize; i++)
    {
        listNode *newNode = new listNode(data[i], NULL);
        lastNode->next = newNode;
        lastNode = newNode;
    }
    cur_Node = firstNode->next;
}

// 析构链表
linkList::~linkList()
{
    listNode *tempNode = firstNode;
    while (tempNode != NULL)
    {
        listNode *nextNode = tempNode->next;
        delete tempNode;
        tempNode = nextNode;
    }
    listSize = 0;
}

// 插入元素(头插法)，成功返回true，失败返回false
bool linkList::headInsertItem(const float &val)
{
    listNode *newNode = new listNode(val, NULL);
    if (newNode == NULL)
    {
        return false;
    }
    newNode->next = firstNode->next;
    firstNode->next = newNode;
    if (cur_Node == firstNode)
    {
        cur_Node = newNode;
    }
    listSize++;
    return true;
}

// 插入元素(尾插法），成功返回true，失败返回false
bool linkList::tailInsertItem(const float &val)
{
    listNode *newNode = new listNode(val, NULL);
    if (newNode == NULL)
    {
        return false;
    }
    lastNode->next = newNode;
    lastNode = newNode;
    if (cur_Node == firstNode)
    {
        cur_Node = newNode;
    }
    listSize++;
    return true;
}

// 插入元素到index位置，成功返回插入位置，错误返回-1
int linkList::insertItem(const int &index, const float &val)
{
    if (index < 0 || index > listSize)
    {
        return -1;
    }
    listNode *newNode = new listNode(val, NULL);
    listNode *letfNode = firstNode;
    for (int i = 0; i < index; i++)
    {
        letfNode = letfNode->next;
    }
    newNode->next = letfNode->next;
    letfNode->next = newNode;
    if (letfNode == lastNode)
    {
        lastNode = newNode;
    }
    listSize++;
    return 0;
}

// 按值删除元素，返回删除位置，找不到返回-1
int linkList::deleteItem(const float &val)
{
    listNode *leftNode = firstNode;
    cur_Node = firstNode->next;
    int index = 0;
    while (cur_Node != NULL)
    {
        if (cur_Node->data == val)
        {
            leftNode->next = cur_Node->next;
            delete cur_Node;
            if (index == listSize - 1)
            {
                lastNode = leftNode;
            }
            listSize--;
            cur_Node = firstNode->next;
            return index;
        }
        index++;
        leftNode = leftNode->next;
        cur_Node = cur_Node->next;
    }
    cur_Node = firstNode->next;
    return -1;
}

// 查找元素（按序号找），成功返回true，值放在val中，失败返回false
bool linkList::locate(const int &index, float &val)
{
    if (index >= listSize || index < 0)
    {
        return false;
    }
    cur_Node = firstNode->next;
    for (int i = 0; i < index; i++)
    {
        cur_Node = cur_Node->next;
    }
    val = cur_Node->data;
    cur_Node = firstNode->next;
    return true;
}

// 查找元素（按值找），返回找到位置，找不到返回-1
int linkList::locate(const float &val)
{
    int index = 0;
    listNode *cur_Node= firstNode->next;
    while (cur_Node != NULL)
    {
        if (cur_Node->data == val)
        {
            return index;
        }
        index++;
        cur_Node = cur_Node->next;
    }
    return -1;
}

// 递增排序
void linkList::ascendingOrder()
{
    listNode *leftNode = firstNode->next;
    while (leftNode->next != NULL)
    {
        listNode *rightNode = leftNode->next;
        while (rightNode != NULL)
        {
            if (rightNode->data < leftNode->data)
            {
                float temp = leftNode->data;
                leftNode->data = rightNode->data;
                rightNode->data = temp;
            }
            rightNode = rightNode->next;
        }
        leftNode = leftNode->next;
    }
}

// 倒序排列元素
void linkList::reverse()
{
    listNode *cur_Node = firstNode->next;
    listNode *pre_Node = NULL;
    while (cur_Node != NULL)
    {
        listNode *next_node = cur_Node->next;
        cur_Node->next = pre_Node;
        pre_Node = cur_Node;
        cur_Node = next_node;
    }
    lastNode = firstNode->next;
    firstNode->next = pre_Node;
    cur_Node = pre_Node;
}
int linkList::getSize()
{
    return listSize;
}
void merge(linkList &A, linkList &B)
{
    for (int i = 0; i < B.getSize(); i++)
    {
        float value;
        B.locate(i, value);
        A.headInsertItem(value);
    }
    A.ascendingOrder();
    A.reverse();
}